คิโดะเกิดที่เมืองฮางิ แคว้นโชชู (ปัจจุบันคือจังหวัดยามางูจิ บนเกาะฮนชู) ประเทศญี่ปุ่น โดยเป็นบุตรคนสุดท้องของวาดะ มาซากาเงะ ผู้เป็นซามูไรและนายแพทย์ เมื่อมีอายุได้ 7 ปี ตระกูลคัตสึระได้รับเขาเป็นบุญธรรม และใช้ชื่อว่า "คัตสึระ โคโงโร" (ญี่ปุ่น: 桂 小五郎 ทับศัพท์: Katsura Kogorō) ไปจนถึง ค.ศ. 1865 ในวัยเด็กนั้นเข้าได้รับการศึกษาจากสำนักเรียนของโยชิดะ โชอิน ซึ่งเป็นผู้ปลูกความคิดเรืองความจงรักภักดีต่อพระจักรพรรดิให้แก่คิโดะ

ในปี ค.ศ. 1852 คิโดะได้เดินทางไปยังนครเอโดะเพื่อศึกษาวิชาดาบเพิ่มเติม และเริ่มติดต่อสัมพันธ์กับกลุ่มซามูไรหัวรุนแรงจากแคว้นมิโตะ ศึกษาวิชาการปืนใหญ่กับเองาวะ ทาโรซาเอมง และเดินทางกลับแคว้นโชชูเพื่อควบคุมการสร้างเรือรบแบบตะวันตกลำแรกของทางแคว้น หลังจากได้สังเกตการต่อเรือเดินทะเลแบบตะวันตกที่เมืองท่านางาซากิและชิโมดะ